package com.gwcloud.leetcode.interview100;

import java.util.HashMap;

/** 
* @ClassName   : Leetcode0149 
* @author      : ganwei 
* @date        : 2020年5月28日 
* @Description : 149. 直线上最多的点数 ，困难
*/
public class Leetcode0149 {
	/**
	 * -解题思路
	 */
    public int maxPoints(int[][] points) {
    	if(points.length < 3) {
    		return points.length;
    	}
    	
    	int res = 0;
    	for(int i = 0; i < points.length; i++) {
    		int duplicate = 0;
    		int max = 0;
    		HashMap<String, Integer> map = new HashMap<>();
    		
    		for(int j = i + 1; j < points.length; j++) {
    			//求分子分母
    			int x = points[j][0] - points[i][0];
    			int y = points[j][1] - points[i][1];
                if (x == 0 && y == 0) {
                    duplicate++;
                    continue;

                }
                //进行约分
                int gcd = gcd(x, y);
                x = x / gcd;
                y = y / gcd;
                String key = x + "@" + y;
                map.put(key, map.getOrDefault(key, 0) + 1);
                max = Math.max(max, map.get(key));
                
    		}
    		res = Math.max(res, max + duplicate + 1);
    	}
    	
    	return res;
    }
    /**
     * -求公约数
     */
    public int gcd(int a, int b) {
    	while(b != 0) {
    		int temp = a % b;
    		a = b;
    		b = temp;
    	}
    	return a;
    }
    
    /**
     * -主函数
     */
    public static void main(String[] args) {
    	
    }
}
